package main

func main() {

}

//在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
//
// 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
//
// 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
//
// 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
//
//
//
// 示例 1：
//
//
//
//输入：root = [1,2,3,4], x = 4, y = 3
//输出：false
//
//
// 示例 2：
//
//
//
//输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
//输出：true
//
//
// 示例 3：
//
//
//
//
//输入：root = [1,2,3,null,4], x = 2, y = 3
//输出：false
//
//
//
// 提示：
//
//
// 二叉树的节点数介于 2 到 100 之间。
// 每个节点的值都是唯一的、范围为 1 到 100 的整数。
//
//
//
// Related Topics 树 广度优先搜索
// 👍 147 👎 0

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isCousins(root *TreeNode, x int, y int) bool {
	type TreeNodeWithDepth struct {
		Depth    int
		TreeNode *TreeNode
	}
	var queue []TreeNodeWithDepth
	queue = append(queue, TreeNodeWithDepth{
		Depth:    0,
		TreeNode: root,
	})

	var xParent, yParent *TreeNode
	var xDepth, yDepth int

	for {
		if len(queue) == 0 {
			break
		}

		// 从队列头中取数据
		node := queue[0]
		queue = queue[1:]

		// 判断是否是要找的数
		if node.TreeNode.Val == x {
			xDepth = node.Depth
		}
		if node.TreeNode.Val == y {
			yDepth = node.Depth
		}

		// 从队列尾部加数据
		if node.TreeNode.Left != nil {
			queue = append(queue, TreeNodeWithDepth{
				Depth:    node.Depth + 1,
				TreeNode: node.TreeNode.Left,
			})
			// 判断是否是要找的数
			if node.TreeNode.Left.Val == x {
				xDepth = node.Depth + 1
				xParent = node.TreeNode
			}
			if node.TreeNode.Left.Val == y {
				yDepth = node.Depth + 1
				yParent = node.TreeNode
			}
		}
		if node.TreeNode.Right != nil {
			queue = append(queue, TreeNodeWithDepth{
				Depth:    node.Depth + 1,
				TreeNode: node.TreeNode.Right,
			})
			// 判断是否是要找的数
			if node.TreeNode.Right.Val == x {
				xDepth = node.Depth + 1
				xParent = node.TreeNode
			}
			if node.TreeNode.Right.Val == y {
				yDepth = node.Depth + 1
				yParent = node.TreeNode
			}
		}
	}

	if xDepth != 0 && yDepth != 0 {
		return xDepth == yDepth && xParent != yParent
	} else {
		return false
	}
}

//leetcode submit region end(Prohibit modification and deletion)
